package leetcode_acm.linkedList;

import org.junit.Test;

import java.util.List;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月20日 22:31
 */

public class MyLinkedList {
    private class ListNode{
        int val;
        ListNode next;
        ListNode prev;
        public ListNode(int val){
            this.val = val;
        }
    }
    private final ListNode dummy;
    private final ListNode tail;

    private int count;

    public MyLinkedList() {
        this.dummy = new ListNode(-1);
        this.tail = new ListNode(-1);
        dummy.next = tail;
        tail.prev = dummy;
        count = 0;
    }

    public int get(int index) {
        //检查下标是否合法
        if(index < 0 || index >= count){
            return -1;
        }
        //1. 将遍历指针指向虚拟的头节点
        ListNode cur = dummy.next;
        //2. 检查index>0?
        while(index >0){
            index -- ;
            cur = cur.next;
        }
        return cur.val;
    }

    public void addAtHead(int val) {
        ListNode newHead = new ListNode(val);
        ListNode oldHead = dummy.next;

        newHead.next = oldHead;
        newHead.prev = dummy;

        dummy.next = newHead;
        oldHead.prev = newHead;

        count++;
    }

    public void addAtTail(int val) {
        ListNode newTail = new ListNode(val);
        ListNode oldTail = tail.prev;

        oldTail.next = newTail;
        newTail.next = tail;

        tail.prev = newTail;
        newTail.prev = oldTail;

        this.count++;
    }

    //void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
    //如果 index 等于链表的长度，那么该节点会被追加到链表的末尾
    //如果 index 比长度更大，该节点将 不会插入 到链表中。
    public void addAtIndex(int index, int val) {
        //要在index-1的位置,找到pre
        if(index < 0 || index > count){
            return ;//不合法
        }
        if(index == 0){
            addAtHead(val);
            return ;
        }
        if(index == count){
            addAtTail(val);
            return ;
        }
        ListNode pre = dummy;
        while(index > 0){
            index--;
            pre = pre.next;
        }
        //此时pre指向了前一个节点,将其new出来
        ListNode newNode = new ListNode(val);

        ListNode oldNode = pre.next;

        oldNode.prev = newNode;
        newNode.next = oldNode;

        pre.next= newNode;
        newNode.prev = pre;

        count++;
    }

    private void deleteFirst(){
        if(count == 0){
            return ;
        }
        ListNode oldHead = dummy.next;
        ListNode headNext = oldHead.next;

        dummy.next = headNext;
        headNext.prev = dummy;

        oldHead.next = oldHead.prev = null;
        count--;
    }

    private void deleteLast(){
        if(count == 0){
            return ;
        }
        ListNode oldTail = tail.prev;
        ListNode tailPrev = oldTail.prev;

        tailPrev.next = tail;
        tail.prev = tailPrev;

        oldTail.next = oldTail.prev = null;

        count--;
    }

    public int size(){
        return this.count;
    }

    public void deleteAtIndex(int index) {
        //先检查下标是否合法
        if(index < 0 || index >= count){
            return ;
        }
        //然后删除节点
        //1. 要删除的节点在头部
        if(index == 0){
            deleteFirst();
            return;
        }

        //2. 要删除的节点在尾部
        if(index == count-1){
            deleteLast();
            return;
        }

        //3.找到pre
        ListNode pre = dummy;
        while(index > 0){
            pre = pre.next;
            index--;
        }
        //4. 通过pre删除这个节点
        ListNode delete = pre.next;
        ListNode next = delete.next;

        pre.next = next;
        next.prev = pre;

        delete.next = delete.prev = null;

        count--;
    }

    @Test
    public void test(){
        MyLinkedList list = new MyLinkedList();
        list.addAtHead(1);
        list.addAtTail(3);
        list.addAtIndex(3,2);
    }

}
